// leetcode 63
// 状态转移方程
// F(m * n)=F((m - 1) * n) + F(m * (n - 1))
// 边界值
// F(2, 2)
export default (arr, m, n) => {
  let dp = (m, n) => {
    // 边界条件
    if (m === 2 && n === 2) {
      // arr[1][1] === 1 || arr[1][0] + arr[0][1] === 2 表示障碍物把路挡上了，此路不通
      // arr[1][0] === 1 || arr[0][1] === 1 表示障碍物当上了其中一条路
      return arr[1][1] === 1 || arr[1][0] + arr[0][1] === 2
        ? 0
        : arr[1][0] === 1 || arr[0][1] === 1
          ? 1
          : 2
    } else if (m < 2 || n < 2) {
      // 单行或单列
      if (m < 2) {
        // 单行中有1就返回0，没有1返回1
        return arr[m - 1].includes(1) ? 0 : 1
      } else {
        // 单列中不能有障碍物（1）有它返回0，没有就返回1
        for (let i = 0; i < m; i++) {
          if (arr[i][0] === 1) {
            return 0
          }
        }
        return 1
      }
    } else {
      // 不是边界就是状态转移方程
      return dp(m - 1, n) + dp(m, n - 1)
    }
  }
  return dp(m, n)
}
